import math
import random
from typing import List


class BaseSegmentTree:

    def __init__(self, n: int):
        self.node_list = [0] * (4 * n)

    def push_up(self, cur_node: int):
        self.node_list[cur_node] = self.node_list[cur_node * 2 + 1] + self.node_list[cur_node * 2 + 2]

    def build(self, nums: List[int], cur_node: int, left: int, right: int):
        if left == right:
            self.node_list[cur_node] = nums[left]
            return
        mid = (left + right) // 2
        self.build(nums, cur_node * 2 + 1, left, mid)
        self.build(nums, cur_node * 2 + 2, mid + 1, right)
        self.push_up(cur_node)

    # 单点增加
    def add(self, num_index: int, value: int, left: int, right: int, cur_node: int):
        if left == right:
            self.node_list[cur_node] += value
            return
        mid = (left + right) // 2
        if num_index <= mid:
            self.add(num_index, value, left, mid, cur_node * 2 + 1)
        else:
            self.add(num_index, value, mid + 1, right, cur_node * 2 + 2)
        self.push_up(cur_node)

    # 单点修改
    def update(self, num_index: int, value: int, left: int, right: int, cur_node: int):
        if left == right:
            self.node_list[cur_node] = value
            return
        mid = (left + right) // 2
        if num_index <= mid:
            self.update(num_index, value, left, mid, cur_node * 2 + 1)
        else:
            self.update(num_index, value, mid + 1, right, cur_node * 2 + 2)
        self.push_up(cur_node)

    # 单点查询
    def query_one(self, num_index: int, left: int, right: int, cur_node: int):
        if left == right:
            return self.node_list[cur_node]
        mid = (left + right) // 2
        if left <= mid:
            return self.query_one(num_index, left, mid, cur_node * 2 + 1)
        else:
            return self.query_one(num_index, mid + 1, right, cur_node * 2 + 2)

    # 区间求和
    def query_range(self, num_left: int, num_right: int, left: int, right: int, cur_node: int):
        if num_left <= left and num_right >= right:
            return self.node_list[cur_node]
        mid = (left + right) // 2
        res = 0
        if num_left <= mid:
            res += self.query_range(num_left, num_right, left, mid, cur_node * 2 + 1)
        if num_right > mid:
            res += self.query_range(num_left, num_right, mid + 1, right, cur_node * 2 + 2)
        return res

    # 区间求最大/最小，记得修改pushup()方法
    def query_range_max(self, num_left: int, num_right: int, left: int, right: int, cur_node: int):
        if num_left <= left and num_right >= right:
            return self.node_list[cur_node]
        mid = (left + right) // 2
        res = math.inf
        if num_left <= mid:
            res = max(res, self.query_range_max(num_left, num_right, left, mid, cur_node * 2 + 1))
        if num_right > mid:
            res = max(res, self.query_range_max(num_left, num_right, mid + 1, right, cur_node * 2 + 2))
        return res

if __name__ == '__main__':
    n = 1000
    nums = [0] * n
    total = [0] * (n + 1)
    for i in range(n):
        nums[i] = random.randint(0, 10000000)
        total[i + 1] = total[i] + nums[i]

    baseSegmentTree = BaseSegmentTree(n)
    baseSegmentTree.build(nums, 0, 0, n - 1)
    for i in range(n):
        left = random.randint(0, n - 1)
        right = random.randint(left, n - 1)
        num_index = random.randint(left, right)
        pre_value = baseSegmentTree.query_range(left, right, 0, n - 1, 0)
        baseSegmentTree.add(num_index, 17, 0, n - 1, 0)
        new_value = baseSegmentTree.query_range(left, right, 0, n - 1, 0)
        print('{}:{} = {}'.format(pre_value, new_value, pre_value + 17 == new_value))
